package cn.jietuo.first.class01;

/**
 * @author zhangx & jietuo_zx@163.com
 * @version 1.0
 * @date 2020/5/27
 * @description: 局部最小值问题
 */
public class Code07_BSAwesome {

    public static int getIndex(int[] arr) {
        if (arr == null || arr.length == 0) {
            return -1;
        }
        // step1: 判断头是否满足
        if (arr.length == 1 || arr[0] < arr[1]) {
            return 0;
        }

        if (arr[arr.length - 1] < arr[arr.length - 2]) {
            return arr.length - 1;
        }

        // 头尾都不符合，使用二分查找
        int l = 1;
        int r = arr.length - 2;
        int mid = 0;
        while (l < r) {
            mid = (r - l) >> 1 + l;
            if ((arr[mid] > arr[mid - 1])) {
                r = mid - 1;
            } else if (arr[mid] > arr[mid + 1]) {
                l = mid + 1;
            } else {
                return mid;
            }
        }
        return l;
    }

}
